# -*- coding: utf-8 -*-

# Ludovic JURADO



### OBSERVATIONS



### OBSERVATIONS



import random
import copy



class AutoCell :
	"""
	Classe pour automate cellulaire personnalisable.

	Le constructeur prend deux arguments obligatoire, tailleX et tailleY - respectivement la largueur et la hauteur de la grille, accessibles sous leur nom en tant qu'attributs -,
	ainsi qu'une multitude d'arguments optionnels dont voici la liste, avec la valeur par défaut, une description et la possibilité (A) ou non (NA) d'y accéder sous ce nom en tant qu'attribut :
	- (A) numEtats (2) : Nombre d'états que peut prendre chaque cellule
	- (A) torus (True) : Topologie du monde. Borné aux limites de la grille ou toroïdal (connection Nord-Sud et Est-Ouest)
	- (A) voisinage (1) : Rayon du voisinage considéré
	- (A) grille (False) : Initialiser avec sa propre grille (matrice 2D de listes correspondant aux dimensions indiquées et composées de cellules dont l'état est >= 0 et < numEtats) ou en générer une aléatoirement
	- (A) regles (False) : Initialiser avec son propre set de règles (états >= 0 et < numEtats, par ex, le jeu de la vie : {0 : {1 : {1 : [3]}}, 1 : {1 : {1 : [2, 3]}}}) ou en générer un aléatoirement
	- (A) poids (False) : Initialiser avec son propre set de poids (liste de matrice 2D de listes affectant des poids au voisinage relatif pour chaque état) ou en générer un automatiquement
	- (NA) seuils (False) : Dans le cas d'une génération aléatoire de la grille, utiliser des seuils pour équilibrer (ou non) le nombre de cellules dans chaque état (sous forme de liste, par ex : [50, 100] pour deux états équilibrés), ou les générer automatiquement
	- (NA) seuilsEq (True) : Dans le cas d'une génération automatique des seuils, les équilibrer où les générer aléatoirement
	- (NA) cellCentrale (False) : Dans le cas d'une génération automatique des poids, compter la cellule centrale ou lui affecter un poids nul (nécessaire pour un automate 'Life-like' par ex)
	- (NA) vonNeumann (False) : Dans le cas d'une génération automatique des poids, affecter un poids nul aux cellules à une trop grande taxi-distance de la cellule centrale pour obtenir un voisinage de Von Neumann (en diamant) ou non (voisinage de Moore, en carré)
	- (NA) totalistique (True) : Dans le cas d'une génération automatique des poids, affecter un poids égal à 1 pour tous les voisins (à la possible exception des voisins concernés par la valeur de cellCentrale et de vonNeumann), ou les générer aléatoirement

	Pour calculer l'étape suivante de l'automate, il suffit d'appeler la méthode etape.

	Exemple d'utilisation pour le jeu de la vie (initialisation de l'automate et calcul et affichage de grille sur une dizaine d'étapes) :

	autoTest = AutoCell(
	tailleX=25, tailleY=25, torus=False,
	regles={0 : {1 : {1 : [3]}}, 1 : {1 : {1 : [2, 3]}}})

	for x in autoTest.grille : print x
	print
	for i in range(10) :
		autoTest.etape()
		for x in autoTest.grille : print x
		print
	"""

	seuilMax = 100

	# initialisation de l'automate avec ses caractéristiques de base
	# on note aussi la possibilité d'initialiser un automate en reprenant tout ou partie des caractéristiques d'un autre
	# par exemple, un cas typique serait de conserver la grille mais de changer les règles
	def __init__(self,
	tailleX, tailleY, grille=False, numEtats=2, torus=True, voisinage=2*[1],
	regles=False, poids=False, seuils=False, seuilsEq=True, typeVois=2*[1],
	totalistique=2*[True]) :
		self.tailleX = tailleX
		self.tailleY = tailleY
		self.numEtats = numEtats
		self.torus = torus # monde toroïdal / monde borné
		self.voisinage = voisinage # rayon de voisinage
		self.seuils = (seuils if seuils else self._genSeuils(seuilsEq))
		self.grille = (grille if grille else self._genGrille())
		self.regles = (regles if regles else self._genRegles())
		if poids :
			self.poids = poids
		else :
			self.poids = []
			for i in range(self.numEtats) :
				self.poids.append(self._genPoids(typeVois[i], totalistique[i], voisinage[i]))



	# génération aléatoire ou équilibrée des densités de base pour les différents états
	# de la forme [33, 66, 100] pour 3 états (exemple équilibré)
	def _genSeuils(self, seuilsEq) :
		seuils = []
		for i in range(1, self.numEtats + 1) :
			seuils.append(((i * AutoCell.seuilMax / self.numEtats) if seuilsEq else random.randint(0, AutoCell.seuilMax)))
		seuils.sort()
		seuils[self.numEtats - 1] = AutoCell.seuilMax
		return seuils

	# génération de la grille 2D
	def _genGrille(self) :
		grille = []
		for x in range(self.tailleX) :
			grille.append([])
			for y in range(self.tailleY) : # on remplit aléatoirement, en tenant compte de la densité voulue
				nbAlea = random.randint(1, AutoCell.seuilMax)
				for i, seuil in enumerate(self.seuils) : # on remplit avec l'état pour lequel le nombre aléatoire se trouve entre les bornes définies
					if nbAlea <= seuil :
						grille[x].append(i)
						break
		return grille



	# génération d'une liste de sous-règles (liste de nombres de cellules vivantes d'un type validant la transition)
	# de la forme [2, 3, 7] par exemple
	def _genSousRegles(self, maxSousRegles) :
		nbSousRegles = random.randint(1, maxSousRegles + 1)
		sousRegles = []
		for i in range(nbSousRegles) :
			sousRegle = random.randint(0, maxSousRegles)
			while sousRegle in sousRegles : sousRegle = random.randint(0, maxSousRegles) # unicité de chaque sous-règle
			sousRegles.append(sousRegle)
		sousRegles.sort()
		return sousRegles

	# génération l'ensemble des règles définissant la transition d'un état donné vers un état "vivant" (!= 0)
	# exemple : Règles du jeu de la vie
	# {
	#	0 : {1 : {1 : [3]}}, # de l'état 0 => état 1 SI 3 voisines dans l'état 1
	#	1 : {1 : {1 : [2, 3]}} # de l'état 1 => état 1 SI 2 OU 3 voisines dans l'état 1
	#	sous-entendu... sinon retour à l'état 0 (par défaut)
	# }
	def _genRegles(self) :
		regles = {}
		for i in range(self.numEtats) : # partant de chaque état de départ
			maxSousRegles = pow((self.voisinage[i] + 1) * 2 - 1, 2) # maximum de sous-règles fonction du voisinage considéré
			regles[i] = {}
			for j in range(1, self.numEtats) : # crée règles conduisant à chaque état dit "vivant" (l'état mort, 0, étant celui par défaut)
				regles[i][j] = {}
				for k in range(1, self.numEtats) :
					regles[i][j][k] = self._genSousRegles(maxSousRegles)
		return regles

	# génération d'une table de multiplicateurs de poids pour chaque état et pour chaque position dans le voisinage
	# par exemple
	# [1, 1, 1]
	# [1, 0, 1]
	# [1, 1, 1]
	# ici la cellule central (pour un état donné) ne compte pas (cas du jeu de la vie par exemple)
	# [0, 1, 0]
	# [1, 1, 1]
	# [0, 1, 0]
	# ici elle compte, mais si tous les états ont la même table, on aura de facto un voisinage de Von Neumann au lieu d'un voisinage de Moore
	def _genPoids(self, typeVois, totalistique, taille) :
		maxMult = pow((taille + 1) * 2 - 1, 2)
		poids = []
		for x in range(taille * 2 + 1) :
			poids.append([])
			for y in range(taille * 2 + 1) :
				if typeVois and x == taille and y == taille : poids[x].append(0)
				elif typeVois == 2 and abs(x - taille) + abs(y - taille) > taille : poids[x].append(0) # taxi-distance pour voisinage de Von Neumann
				elif typeVois and totalistique : poids[x].append(1) # toutes les positions se valent si totalistique
				elif totalistique : poids[x].append(random.randint(0, 1))
				else : poids[x].append(random.randint(0, maxMult))
		return poids


	# analyse du voisinage
	def _explore(self, grilleCopie, x, y) :
		vois = self.voisinage[grilleCopie[x][y]] # taille du voisinage pour l'état considéré
		voisins = self.numEtats * [0]
		for vx in range(x - vois, x + vois + 1) :
			if self.torus : vxc = (vx + self.tailleX) % self.tailleX # si monde toroïdal, on boucle Nord-Sud...
			elif vx < 0 or vx >= self.tailleX : continue # sinon on vérifie qu'il n'y a pas de dépassement
			else : vxc = vx
			vxr = vx - x + vois # position voisin relative
			for vy in range(y - vois, y + vois + 1) :
				if self.torus : vyc = (vy + self.tailleY) % self.tailleY # ... et Est-Ouest (si monde toroïdal)
				elif vy < 0 or vy >= self.tailleY : continue
				else : vyc = vy
				voisins[grilleCopie[vxc][vyc]] += 1 * self.poids[grilleCopie[x][y]][vxr][vy - y + vois] # on tient du compte du poids de la position
		return voisins

	# application de la transition d'une cellule d'un état à l'autre en fonction de l'ensemble de règles et de son voisinage
	def _transition(self, x, y, voisins) :
		for etatCible, regle in self.regles[self.grille[x][y]].items() :
			transTrouvee = True
			for etatVoisin, sousRegles in regle.items() :
				if voisins[etatVoisin] not in sousRegles :
					transTrouvee = False
					break
			if transTrouvee : # le voisinage de la cellule permet la transition vers un état "vivant"
				self.grille[x][y] = etatCible
				break
		if not transTrouvee : self.grille[x][y] = 0 # sinon la cellule meurt

	# fonction pilotant le passage à l'étape suivante pour l'ensemble des cellules de la grille
	def etape(self) :
		grilleCopie = copy.deepcopy(self.grille) # il ne faut pas modifier la grille alors qu'on la parcourt, donc on réalise une copie
		for x in range(self.tailleX) :
			for y in range(self.tailleY) : # pour chaque cellule de la grille, on explore le voisinage et on change d'état en fonction de lui
				self._transition(x, y, self._explore(grilleCopie, x, y))
